package hot100.哈希;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * @ https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
 * @date 2025/08/23
 */
public class 最长连续序列_128 {

    public static void main(String[] args) {

    }

    /**
     * 往前，往后遍历连续的数字，遍历过的数字不需要再遍历
     */
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        Set<Integer> visitedSet = new HashSet<>();
        for (Integer num : set) {
            int curCnt = 1;
            int curNum = num + 1;
            while (!visitedSet.contains(curNum) &&
                    set.contains(curNum)) {
                visitedSet.add(curNum);
                curCnt++;
                curNum++;
            }
            curNum = num - 1;
            while (!visitedSet.contains(curNum) &&
                    set.contains(curNum)) {
                visitedSet.add(curNum);
                curCnt++;
                curNum--;
            }

            ans = Math.max(ans, curCnt);
        }
        return ans;
    }

    // TODO 只遍历连续数字的最小的那个数字作为起点

}
